import java.util.Scanner;

public class Test {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}


 class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 如果两个树都为空，它们相同
        if (p == null && q == null) {
            return true;
        }
        // 如果只有一个树为空，它们不相同
        if (p == null || q == null) {
            return false;
        }
        // 如果根节点的值不相等，它们不相同
        if (p.val != q.val) {
            return false;
        }
        // 递归比较左子树和右子树
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    public boolean isSameTree2(TreeNode p, TreeNode q) {
        // 如果两个树都为空，它们相同
        if (p == null && q == null) {
            return true;
        }

        // 如果只有一个树为空，它们不相同
        if (p == null || q == null) {
            return false;
        }
/*        if (p != null && q == null||p == null && q != null) {
            return false;
        }*/
        // 如果根节点的值不相等，它们不相同
        if (p.val != q.val) {
            return false;
        }
        // 递归比较左子树和右子树
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
/*    时间复杂度：O（r*s）
    root  r
    subroot s   */
    private boolean isSubTree(TreeNode root, TreeNode subRoot) {
        if(root==null){
            return false;
        }
        if(isSameTree(root,subRoot)){
            return true;
        }
        if (isSubTree(root.left,subRoot)) {
            return true;
        }
        if (isSubTree(root.right,subRoot)) {
            return true;
        }
        return false;
    }
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        // 递归地翻转左右子树
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 检查当前节点的左右子树的高度差是否超过1
        if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) {
            return false;
        }
/*        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        if(Math.abs(leftHeight-rightHeight)<=1){
            return false;
        }*/
        // 递归地检查左子树和右子树是否都是高度平衡的
        return isBalanced(root.left) && isBalanced(root.right);
    }

    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 递归地计算节点的高度
        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);
        // 返回节点的高度（左右子树中较大的高度加上1）
        return (leftHeight>rightHeight?leftHeight+1:rightHeight+1);
    }
    public boolean isBalanced2(TreeNode root) {
        if (root == null) {
            return true;
        }
        return getHeight(root)>=0;
    }
    private int getHeight2(TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 递归地计算节点的高度
        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);
        if(leftHeight>=0&&rightHeight>=0&& Math.abs(leftHeight-rightHeight)<=1){
            return Math.max(leftHeight,rightHeight)+1;
        }else {
            return -1;
        }
    }
/*    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }

        // 使用缓存来存储节点的高度
        Map<TreeNode, Integer> heightMap = new HashMap<>();

        return isBalancedHelper(root, heightMap);
    }

    private boolean isBalancedHelper(TreeNode node, Map<TreeNode, Integer> heightMap) {
        if (node == null) {
            return true;
        }

        // 检查缓存中是否已经存储了节点的高度
        if (heightMap.containsKey(node)) {
            return heightMap.get(node) != -1; // 高度为-1表示节点不平衡
        }

        // 递归地检查左子树和右子树是否都是高度平衡的
        boolean leftBalanced = isBalancedHelper(node.left, heightMap);
        boolean rightBalanced = isBalancedHelper(node.right, heightMap);

        // 计算节点的高度并存储到缓存中
        int leftHeight = getHeight(node.left, heightMap);
        int rightHeight = getHeight(node.right, heightMap);
        int currentHeight = Math.max(leftHeight, rightHeight) + 1;
        heightMap.put(node, currentHeight);

        // 检查当前节点的左右子树的高度差是否超过1
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return false;
        }

        return leftBalanced && rightBalanced;
    }

    private int getHeight(TreeNode node, Map<TreeNode, Integer> heightMap) {
        if (node == null) {
            return 0;
        }

        // 检查缓存中是否已经存储了节点的高度
        if (heightMap.containsKey(node)) {
            return heightMap.get(node);
        }

        // 递归地计算节点的高度
        int leftHeight = getHeight(node.left, heightMap);
        int rightHeight = getHeight(node.right, heightMap);

        // 计算节点的高度并存储到缓存中
        int currentHeight = Math.max(leftHeight, rightHeight) + 1;
        heightMap.put(node, currentHeight);

        return currentHeight;
    }*/
     public boolean isSymmetric(TreeNode root) {
  if (root == null) {
 return true;
}
 return isMirror(root.left, root.right);
 }

 private boolean isMirror(TreeNode left, TreeNode right) {
 if (left == null && right == null) {
 return true;
}
 if (left == null || right == null || left.val != right.val) {
 return false;
 }
 if(left==null&&right!=null||right==null&&left!=null){
     return false;
 }
 return isMirror(left.left, right.right) && isMirror(left.right, right.left);
 }
/* import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

    class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;

        TreeNode(char val) {
            this.val = val;
        }
    }

    public class Main {
        // 注意类名必须为 Main，不要有任何 package xxx 信息 public class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);// 注意hasNext 和hasNextLine的区别
            while (in.hasNextLine()) { // 注意 while 处理多个 case
                String str = in.nextLine();
                TreeNode root = creatrTree(str);
                inorder(root);
            }
        }

        public static  int i = 0;

        public static TreeNode creatrTree(String str) {
            TreeNode root = null;

            if (str.charAt(i) != '#') {
                root = new TreeNode(str.charAt(i));
                i++;
                root.left = creatrTree(str);
                root.right = creatrTree(str);
            } else {
                i++;
            }
            return root;
        }



        public static void inorder(TreeNode root) {
            if (root == null) {
                return;
            }
            inorder(root.left);
            System.out.print(root.val + " ");
            inorder(root.right);

        }
    }*/
}
